// https://www.lintcode.com/problem/reverse-linked-list-ii/

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param head: ListNode head is the head of the linked list 
     * @param m: An integer
     * @param n: An integer
     * @return: The head of the reversed ListNode
     */
    public ListNode reverseBetween(ListNode head, int m, int n) {
        // write your code here
        ListNode dummy = new ListNode(0); // 简化head的处理
        dummy.next = head;
        ListNode tmp_head = dummy, tmp_tail = dummy;
        ListNode prev = null;
        for (int i = 0; i < n; ++i) { // 把m到n这段标记出来
            if (i < m) {
                prev = tmp_head;
                tmp_head = tmp_head.next;
            }
            tmp_tail = tmp_tail.next;
        }
        ListNode next = tmp_tail.next; // 记录一下第n个节点后的节点
        tmp_tail.next = null;
        tmp_head = reverse(tmp_head);
        prev.next = tmp_head;
        while (tmp_head.next != null) {
            tmp_head = tmp_head.next;
        }
        tmp_head.next = next;
        return dummy.next;
    }
    
    private ListNode reverse(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode new_head = null;
        while (head != null) {
            ListNode node = head;
            head = head.next;
            node.next = new_head;
            new_head = node;
        }
        return new_head;
    } 
}